/**
 * FileName:Exercise1405.c
 * ------------------------------------------------------------------------------------------------------------
 * 14.5 Write a program to compute the $\chi^{2}$ statistic for the hash values of $N$ keys with table size $M$.
 * This number is defined by the equation
    $$
    \chi^{2}=\frac{M}{N} \sum_{0 \leq i<M}\left(f_{i}-\frac{N}{M}\right)^{2},
    $$
 * where $f_{i}$ is the number of keys with hash value $i$.
 *
 * If the hash values are random, this statistic, for $N>c M$, should be $M \pm \sqrt{M}$ with probability $1-1/c$.
 * ------------------------------------------------------------------------------------------------------------
 */

#include <stdio.h>
#include <stdlib.h> // For malloc, free, rand, srand
#include <time.h>   // For time (to seed rand)
#include <math.h>   // For sqrtf (optional, but good for context)

// --- 哈希函数定义 ---
int hash_1406(int x, int M) {
    // 选用一个大素数作为乘数 'a'
    // 确保中间乘积不会溢出 int，可以使用 long long
    return (int)(((long long)618033 * x) % M);
}

// --- 计算 Chi-Squared 统计量的函数 ---
// 参数：
//   hash_func: 一个指向哈希函数的指针，该函数接受一个键和一个表大小 M 并返回一个哈希值
//   N: 键的数量
//   M: 哈希表的尺寸
//   key_value_limit: 随机生成键的最大值（例如，如果键范围是 [0, key_value_limit-1]）
float calculate_chi_square(int (*hash_func)(int, int), int N, int M, int key_value_limit) {
    // 1. 初始化计数数组 f_i
    int* f_i = (int*)calloc(M, sizeof(int)); // calloc 初始化为0
    if (f_i == NULL) {
        perror("Failed to allocate memory for f_i count array");
        return -1.0f; // Indicate error
    }

    // 2. 生成 N 个随机键并计算哈希值，更新 f_i
    // 为了生成更广泛的随机数，可以使用组合 rand() 或考虑 C++11 的 <random>
    // 这里简化为 rand() % key_value_limit
    for (int i = 0; i < N; i++) {
        // 生成一个随机键
        int key = rand() % key_value_limit;
        // 计算哈希值
        int hash_val = hash_func(key, M);

        // 确保哈希值在有效范围内，防止数组越界
        if (hash_val < 0 || hash_val >= M) {
            fprintf(stderr, "Error: Hash value %d out of bounds [0, %d) for key %d.\n", hash_val, M, key);
            free(f_i);
            return -2.0f; // Indicate error
        }
        f_i[hash_val]++;
    }

    // 3. 计算期望的平均频率 N/M
    float expected_avg_freq = (float)N / M;

    // 4. 计算 Chi-Squared 统计量
    float chi_square_sum = 0.0f;
    for (int i = 0; i < M; i++) {
        float difference = f_i[i] - expected_avg_freq;
        chi_square_sum += difference * difference;
    }

    // 最终的 Chi-Squared 公式：(M/N) * sum_of_squares
    float chi_square = ( (float)M / N ) * chi_square_sum;

    // 释放内存
    free(f_i);

    return chi_square;
}

// --- 测试函数 ---
void test_hash_rand() {
    // 设定 N 和 M 的值
    int N = 100000; // 键的数量
    int M = 100;   // 哈希表的大小

    // 确保 N > M * c (例如 c=10) 以符合统计学上的建议，即 N > 10 * M
    if (N < 10 * M) {
        fprintf(stderr, "Warning: N (%d) is not significantly larger than M (%d), chi-square statistic might be less reliable.\n", N, M);
        fprintf(stderr, "Consider setting N to at least 10 * M.\n");
    }

    int key_value_limit = 1000000; // 随机键的范围，例如从 0 到 999999

    // 初始化随机数生成器
    srand(time(NULL));

    printf("Calculating Chi-Squared statistic for N=%d keys and M=%d table size.\n", N, M);
    printf("Using random keys from 0 to %d.\n", key_value_limit - 1);

    // 调用 calculate_chi_square 函数
    float chi_square_result = calculate_chi_square(hash_1406, N, M, key_value_limit);

    if (chi_square_result >= 0) {
        printf("Computed Chi-Squared (X^2) = %f\n", chi_square_result);

        // 根据理论，如果哈希值是随机的，X^2 应该在 M +- sqrt(M) 左右
        float expected_mean = (float)M;
        float expected_std_dev = sqrtf((float)M);
        printf("Expected X^2 for random values (M +- sqrt(M)): %f +- %f\n", expected_mean, expected_std_dev);

        // 添加统计显著性判断
        float lower_bound = M - sqrt(M);
        float upper_bound = M + sqrt(M);
        if (chi_square_result > lower_bound && chi_square_result < upper_bound) {
            printf("Result PASSES randomness test (within M ± √M)\n");
        } else {
            printf("Result FAILS randomness test\n");
        }
    } else {
        printf("Error during Chi-Squared calculation.\n");
    }
}

// --- Main 函数 ---
int main(int argc, char *argv[]) {
    test_hash_rand();
    return 0;
}